#include <iostream>

using namespace std;

const int LIMIT = 1024;

int opt[LIMIT];
int costs[LIMIT];

void initialize(void) {
	for(int i = 0; i < LIMIT; ++i) {
		opt[i] = -1;
	}

	opt[0] = 0;
	costs[0] = 0;
}

int solve(int right) {
	if(opt[right] != -1) {
		return opt[right];
	}

	int max = -1;

	for(int left = 1; left < right; ++left) {
		int lopt = solve(left) + solve(right-left);

		if(lopt > max) {
			max = lopt;
		}
	}

	if(costs[right] > max) {
		max = costs[right];
	}

	opt[right] = max;

	return max;
}

int main(int argc, char* argv[]) {
	initialize();

	int n;

	cin >> n;

	if(n > LIMIT) {
		cerr << "Please specify a number less that " << LIMIT << endl;
		return -1;
	}

	for(int i = 0; i < n; ++i) {
		cin >> costs[i + 1];
	}

	opt[1] = costs[1];

	solve(n);

	cout << "Costs   :";
	for(int i = 1; i <= n; ++i) {
		cout << " " << costs[i];
	}
	cout << endl;

	cout << "Solution:";
	for(int i = 1; i <= n; ++i) {
		cout << " " << opt[i];
	}
	cout << endl;

	return 0;
}

